package sword.chapter8Tree;

import java.util.HashMap;

/**
 * 向下的路径结点之和
 *
 * 深度优先搜索 前序遍历 + map哈希表
 * 细节
 * 1. 先累加路径之和
 * 2. 获取path-sum出现次数
 * 3. 存入path路径之和（之前存在，需要累加）
 * 4. 遍历完当前节点的左右分支后，需要在map中移除当前节点的路径之和，避免其它分支重复获取。
 *
 * @author K
 * @date 2021/12/7 15:28
 */
public class S50PathSum {
    public static int s50(TreeNode root, int sum) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return dfs(root, map, sum, 0);
    }

    private static int dfs(TreeNode root, HashMap<Integer, Integer> map, int sum, int path) {
        if (root == null) {
            return  0;
        }
        path += root.val;
        // 获取历史路径和出现的次数
        Integer count = map.getOrDefault(path - sum, 0);
        // 将当前路径之和path存入到map中，如果原来已经存有数据，需要累加（主要是排除节点值为0的情况）
        map.put(path, map.getOrDefault(path, 0) + 1);
        count += dfs(root.left, map, sum, path);
        count += dfs(root.right, map, sum, path);

        // 需要将map中的path对应出现的次数-1，避免其它分支重复获取。
        map.put(path, map.get(path) - 1);
        return count;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node2 = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);
        TreeNode node1 = new TreeNode(1);
        TreeNode node6 = new TreeNode(6);
        TreeNode node3 = new TreeNode(3);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node4;
        node2.left = node1;
        node2.right = node6;
        node4.left = node3;
        node4.right = node7;

        TreeNode rootA = new TreeNode(0);
        TreeNode nodeA1 = new TreeNode(1);
        TreeNode nodeA2 = new TreeNode(1);

        rootA.left = nodeA1;
        rootA.right = nodeA2;


//        int result = s50(root, 8);
        int result2 = s50(rootA, 1);
        System.out.println();
    }
}
